//
// Created by Mr.J on 2019/11/1.
//
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int maxProfit(std::vector<int>& prices) {
    if(prices.empty())return 0;
    int day = prices.size();
    int dp[day][2][2];
    memset(dp,0, sizeof(dp));
    dp[0][0][0] = 0;
    dp[0][0][1] = -prices[0];
    dp[0][1][0] = 0;
    dp[0][1][1] = -prices[0];
    for (int i = 1; i < day; ++i) {
        dp[i][0][0] = max(dp[i-1][0][0],dp[i-1][0][1]+prices[i]);
        dp[i][0][1] = max(dp[i-1][1][0]-prices[i],dp[i-1][0][1]);
        dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]);
        dp[i][1][1] = max(dp[i-1][1][1],-prices[i]);
    }
    return dp[day-1][0][0];
}

int main(){
    std::vector<int>b = {3,3,5,0,0,3,1,4};

    std::cout<<maxProfit(b)<<std::endl;
    return 0;
}